109. 有序链表转换二叉搜索树

Similar Question

leading to the advanced question

Solution Tips

方案一: 真正的中序遍历完成构建

108 的数组构造中, 其实是前序递归构造的.

但是其实也可以使用中序遍历完成构造, 就是优先构造最左侧的节点. 关键就是知道 root 的位置就可以了.

const sortedListToBST = (head) => {
  if (head == null) return null;
  let len = 0;
  let h = head;  // h初始指向头结点
  while (head) { // 计算链表节点个数
    len++;
    head = head.next;
  }

  const buildBST = (start, end) => {
    if (start > end) return null;     // 递归出口，返回null节点
    const mid = (start + end) >>> 1;  // 求mid，只是为了分治，不是用它断开链表
    const left = buildBST(start, mid - 1); // 先递归构建左子树

    const root = new TreeNode(h.val);      // 根据 h.val 构建节点
    h = h.next;          // h指针步进              
    root.left = left;    // root接上构建好的左子树        

    root.right = buildBST(mid + 1, end); // 构建当前root的右子树，接上
    return root;
  };

  return buildBST(0, len - 1);
};